package oj;

import java.util.*;

public class LC797 {
    //BFS解法
//    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
//        int n=graph.length;
//        List<List<Integer>> list=new ArrayList<>();
//        Queue<List<Integer>> q=new LinkedList<>();
//        q.add(new ArrayList<>(){{add(0);}});
//        while(q.size()>0){
//            List<Integer> path=q.poll();
//            int temp=path.get(path.size()-1);
//            if(temp==n-1){
//                list.add(path);
//            }
//            for(int y:graph[temp]){
//                List<Integer> temp2=new ArrayList<>(path);
//                temp2.add(y);
//                q.add(temp2);
//            }
//        }
//        return list;
//    }

    //DFS解法
    List<List<Integer>> list=new ArrayList<>();
    Deque<Integer> stack=new ArrayDeque<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n=graph.length;
        if(n==0) return new ArrayList<>();
        stack.addLast(0);
        dfs(graph,0,n-1);
        return list;

    }
    private void dfs(int[][] graph,int i,int j){
        if(i==graph.length-1){
            list.add(new ArrayList<>(stack));
            return;
        }
        for(int y:graph[i]){
            stack.add(y);
            dfs(graph,y,graph.length-1);
            stack.pollLast();
        }

    }
}
